高等代数，第四版，第三章P158，T21

数学兴趣大讲堂

---

递归论

递归论或可计算性理论，是一个数理逻辑分支。它起源于可计算函数和图灵度的研究。它的领域增长为包括一般性的可计算性和可定义性的研究。在这些领域中，这门理论同证明论和能行描述集合论（effective descriptive set theory）有所重叠。

数理逻辑中的可计算性理论家经常研究相对可计算性、可归约性概念和程度结构的理论。相对于计算机科学家，他们研究次递归层次，可行的计算和公用于可计算性理论研究的形式语言。在这两个社区之间有着相当大的知识和方法上的重叠，而没有明显的界限。

递归论所考虑的基本问题是，给定一个从自然数到自然数的函数f，f是否是可以被计算的。“可以被计算”，我们先将其当作一个直观的概念。根据直觉，人们一般会认为，一个函数可以被计算是存在一个给定的过程，接受一个自然数n后，该过程进行一定的操作并给出f(n)作为输出。将计算这一直观的概念上升到数学层面的形式化定义这一工作是递归论的根本，并由哥德尔、邱奇、图灵、克莱尼和Emil Post等人在1930年代奠定。他们将图灵可计算性作为有效计算的形式化。

在递归论的基本概念被给定之后，一方面人们将该观念应用于数学中，从而证明了一系列自然的问题，如字问题，以及希尔伯特第十问题等问题是不可计算的。另一方面，理论家们进一步拓展，开始了相对可计算性，图灵度等问题的研究。如今，递归论仍是数理逻辑中活跃的领域。

递归论理论起源自哥德尔、邱奇、图灵、克莱尼和Emil Post在1930年代的工作。他们获得的基本结果建立了图灵可计算性作为有效计算的非正式想法的正确的形式化。通过能行计算的严格定义带来了在数学中有些问题是不可有效判定的最初证明。邱奇和图灵独立的证明了停机问题不能进行判定，而Post证明了在Thue系统中确定一个字符串是否有规范形式（类似于在λ演算中一个项是否有规则形式）不能有效的确定。

不可解度结构的研究，包括图灵度、多一度和类似的结构，是这个领域的重要部分。图灵度的研究发起自Kleene和Post [1954]。大量的可计算性理论中的研究已经投入到图灵度的性质的研究中。开始于1970年代，图灵度的研究焦点已经从局部结构性质转移到全局性质，比如图灵度的自同构（automorphism）和 {displaystyle 0'}的可定义性。

在1930年代确定了最初的例子之后，很多数学问题已经被证实是不可判定的。Novikov和Boone在1950年代证实，给出在一个有限出现群中的一个字，没有有效的过程来判定这个字所表示的元素是否是这个群的单位元素。这个结果被用来证实很多其他问题是不可判定的，比如两个有限单形（simplicial complex）是否表现同胚空间的问题。在1970年，尤里·马季亚谢维奇对希尔伯特第十问题给出了否定答案，它提问是否有有效的过程来判定有有限多个有理数上的变量的丢番图方程是否有在有理数上的解。这个否定解答是对Martin Davis、Hilary Putnam和Julia Robinson在1961年给出的部分解答的巩固。

递归论包括可计算性的一般概念的研究，比如超算术可归约性（hyperarithmetic degrees）、α-递归论和可构成度（constructibility degrees）。

精选推荐

01
02	数学各学科：全套高清图的获取方式
03

■ END ■

第一章A组答案：  1  |   2  |   3  |   4  |   5  |   6  |   7  |   8  |   9  |  10  |  11  |  12  |  13  |  14  |  15  |  16  |  17  |  18  |  19  |  20  |  21  |  22  |  23  |  24  |  25  |  26  |  27 |  28  |  29  |  30  |  31  |  32

第二章A组答案：1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |  10  |  11  |  12  |  13  |  14  |   15  |  16  |  17  |  18  |  19  |  20  

课后习题视频系列：  第四章A组  |  第五章A组   

高代资料系列：高代各章知识框架全解  |  数学各学科分支图解  |  高代资料书推荐  |  Eisenstein判别法的深入分析  |  整除中难题分析 |  整数的带余除法定理  |  最大公因式证明题  |  什么是高等代数

数学学科排名： 2018数学学科排名  |  2019数学学科排名  

英语：四六必过宝典 

数学兴趣：用数学公式怎样表白  |  研究生丛书（GTM） |  公式转化为LaTex代码  |  如何注册arXiv  |  MathSciNet 使用指南  |  惊呆！数学公式推导出圣诞节

数分：实数系六大定理互证(一)  |  实数系六大定理互证(二)   |   实数系六大定理互证(三)

考研系列

中南大学高代真题及答案：2012年 | 2013年 | 2014年

未经允许，禁止转载

钟哥数学博士团队介绍：      团队是由国内数学“一流学科”博士组成，接受了国内顶尖教授导师的培养，数学专业知识扎实、素质过硬，博士团队有着丰富的数学（高代、数分等）基础课程的教学经验，以及数学资料的研发与制作经验。   
    高代学习QQ交流群：945166269. 加入高代数分交流微信群请加助手微信：zhongyuemingmit

让我知道你在看